/*------------------------------------------------------------------------
 *
 * geqo_pool.c
 *	  遗传算法（GA）池的内容
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/backend/optimizer/geqo/geqo_pool.c
 *
 *-------------------------------------------------------------------------
 */

/* 贡献者：
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   *  Martin Utesch				 * 自动控制研究所		   *
   =							 = 矿业与技术大学 =
   *  utesch@aut.tu-freiberg.de  * 德国弗赖贝格				   *
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */

/* -- 这部分的内容改编自 D. Whitley 的 Genitor 算法 -- */

#include "postgres.h"

#include <float.h>
#include <limits.h>
#include <math.h>

#include "optimizer/geqo_copy.h"
#include "optimizer/geqo_pool.h"
#include "optimizer/geqo_recombination.h"


static int	fc_compare(const void *fc_arg1, const void *fc_arg2);

/*
 * alloc_pool
 * 分配 GA 池的内存
 */
Pool *
alloc_pool(PlannerInfo *fc_root, int fc_pool_size, int fc_string_length)
{
	Pool	   *fc_new_pool;
	Chromosome *fc_chromo;
	int			fc_i;

	/* pool */
	fc_new_pool = (Pool *) palloc(sizeof(Pool));
	fc_new_pool->size = (int) fc_pool_size;
	fc_new_pool->string_length = (int) fc_string_length;

	/* 所有染色体 */
	fc_new_pool->data = (Chromosome *) palloc(fc_pool_size * sizeof(Chromosome));

	/* all gene */
	fc_chromo = (Chromosome *) fc_new_pool->data; /* 所有染色体的向量 */
	for (fc_i = 0; fc_i < fc_pool_size; fc_i++)
		fc_chromo[fc_i].string = palloc((fc_string_length + 1) * sizeof(Gene));

	return fc_new_pool;
}

/*
 * free_pool
 * 释放 GA 池的内存
 */
void free_pool(PlannerInfo *fc_root, Pool *fc_pool)
{
	Chromosome *fc_chromo;
	int			fc_i;

	/* all gene */
	fc_chromo = (Chromosome *) fc_pool->data; /* 所有染色体的向量 */
	for (fc_i = 0; fc_i < fc_pool->size; fc_i++)
		pfree(fc_chromo[fc_i].string);

	/* 所有染色体 */
	pfree(fc_pool->data);

	/* pool */
	pfree(fc_pool);
}

/*
 * random_init_pool
 * 初始化遗传池
 */
void random_init_pool(PlannerInfo *fc_root, Pool *fc_pool)
{
	Chromosome *fc_chromo = (Chromosome *) fc_pool->data;
	int			fc_i;
	int			fc_bad = 0;

	/*
	 * 我们立即丢弃任何无效个体（geqo_eval 返回 DBL_MAX 的那些），
	 * 从而不浪费池空间于它们。
	 *
	 * 如果在 10000 次尝试后未能产生任何有效个体，则放弃；
	 * 这可能意味着某些东西出错了，我们不应仅仅让自己陷入无限循环。
	 */
	fc_i = 0;
	while (fc_i < fc_pool->size)
	{
		init_tour(fc_root, fc_chromo[fc_i].string, fc_pool->string_length);
		fc_pool->data[fc_i].worth = geqo_eval(fc_root, fc_chromo[fc_i].string,
										fc_pool->string_length);
		if (fc_pool->data[fc_i].worth < DBL_MAX)
			fc_i++;
		else
		{
			fc_bad++;
			if (fc_i == 0 && fc_bad >= 10000)
				elog(ERROR, "geqo failed to make a valid plan");
		}
	}

#ifdef GEQO_DEBUG
	if (fc_bad > 0)
		elog(DEBUG1, "%d invalid tours found while selecting %d pool entries",
			 fc_bad, fc_pool->size);
#endif
}

/*
 * sort_pool
 * 按照价值对输入池进行排序，从最小到最大
 *
 * 你可能需要为不同的排序更改 compare() ...
 */
void sort_pool(PlannerInfo *fc_root, Pool *fc_pool)
{
	qsort(fc_pool->data, fc_pool->size, sizeof(Chromosome), fc_compare);
}

/*
 * compare
 * qsort 比较函数用于 sort_pool
 */
static int fc_compare(const void *fc_arg1, const void *fc_arg2)
{
	const Chromosome *fc_chromo1 = (const Chromosome *) fc_arg1;
	const Chromosome *fc_chromo2 = (const Chromosome *) fc_arg2;

	if (fc_chromo1->worth == fc_chromo2->worth)
		return 0;
	else if (fc_chromo1->worth > fc_chromo2->worth)
		return 1;
	else
		return -1;
}


/* alloc_chromo
 *	  分配一个染色体和字符串空间
 */
Chromosome *
alloc_chromo(PlannerInfo *fc_root, int fc_string_length)
{
	Chromosome *fc_chromo;

	fc_chromo = (Chromosome *) palloc(sizeof(Chromosome));
	fc_chromo->string = (Gene *) palloc((fc_string_length + 1) * sizeof(Gene));

	return fc_chromo;
}

/* free_chromo
 *	  解除分配一个染色体和字符串空间
 */
void free_chromo(PlannerInfo *fc_root, Chromosome *fc_chromo)
{
	pfree(fc_chromo->string);
	pfree(fc_chromo);
}

/* spread_chromo
 * 插入一个新的染色体到池中，取代池中最差的基因
 * 假设最佳->最差 = 最小->最大
 */
void spread_chromo(PlannerInfo *fc_root, Chromosome *fc_chromo, Pool *fc_pool)
{
	int			fc_top,
				fc_mid,
				fc_bot;
	int			fc_i,
				fc_index;
	Chromosome	fc_swap_chromo,
				fc_tmp_chromo;

	/* 新染色体太差，无法使用 */
	if (fc_chromo->worth > fc_pool->data[fc_pool->size - 1].worth)
		return;

	/* 进行二分搜索以找到新染色体的索引 */

	fc_top = 0;
	fc_mid = fc_pool->size / 2;
	fc_bot = fc_pool->size - 1;
	fc_index = -1;

	while (fc_index == -1)
	{
		/* 这4种情况寻找新的位置 */

		if (fc_chromo->worth <= fc_pool->data[fc_top].worth)
			fc_index = fc_top;
		else if (fc_chromo->worth == fc_pool->data[fc_mid].worth)
			fc_index = fc_mid;
		else if (fc_chromo->worth == fc_pool->data[fc_bot].worth)
			fc_index = fc_bot;
		else if (fc_bot - fc_top <= 1)
			fc_index = fc_bot;


		/*
		 * 这2种情况移动搜索索引，因为尚未找到新位置。
		 */

		else if (fc_chromo->worth < fc_pool->data[fc_mid].worth)
		{
			fc_bot = fc_mid;
			fc_mid = fc_top + ((fc_bot - fc_top) / 2);
		}
		else
		{						/* (chromo->worth > pool->data[mid].worth) */
			fc_top = fc_mid;
			fc_mid = fc_top + ((fc_bot - fc_top) / 2);
		}
	}							/* ... 当 */

	/* 现在我们有了染色体的索引 */

	/*
	 * 将从索引开始的每个基因向下移动一个位置以为染色体腾出空间
	 */

	/*
	 * 将新的基因复制到池存储中；总是替换池中最差的基因
	 */

	geqo_copy(fc_root, &fc_pool->data[fc_pool->size - 1], fc_chromo, fc_pool->string_length);

	fc_swap_chromo.string = fc_pool->data[fc_pool->size - 1].string;
	fc_swap_chromo.worth = fc_pool->data[fc_pool->size - 1].worth;

	for (fc_i = fc_index; fc_i < fc_pool->size; fc_i++)
	{
		fc_tmp_chromo.string = fc_pool->data[fc_i].string;
		fc_tmp_chromo.worth = fc_pool->data[fc_i].worth;

		fc_pool->data[fc_i].string = fc_swap_chromo.string;
		fc_pool->data[fc_i].worth = fc_swap_chromo.worth;

		fc_swap_chromo.string = fc_tmp_chromo.string;
		fc_swap_chromo.worth = fc_tmp_chromo.worth;
	}
}
